#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 空间复杂度为 O(1)，时间复杂度为 O(n)
    bool canJump(vector<int>& nums) {
        int n = nums.size();

        // 状态：f[i] 表示 1 ~ i 能够跳到最远的位置
        // int f[n];
        int k = nums[0];

        // f[0] = nums[0];

        for (int i = 1; i < n; i++) {
            // i - 1 跳不到当前的位置，那么退出
            // if (f[i - 1] < i) {
            //     return false;
            // }

            if (k < i) {
                return false;
            }

            // 状态转移方程：要不就是之前能够跳到的最远位置
            // 要不就是当前能够跳到的最远位置
            // f[i] = max(f[i - 1], i + nums[i]);
            k = max(k, i + nums[i]);

            // if (f[i] >= n - 1) {
            //     return true;
            // }
            // 如果能够跳到最后一个位置，提前结束
            if (k >= n - 1) {
                return true;
            }
        }

        return true;
    }
};